DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.18

On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges

Authors: Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, and Tommaso Piselli

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applications. In particular, an st-orientation orients each edge of the input graph such that the resulting digraph is acyclic, and it contains a single source s and a single sink t. Computing an st-orientation of a graph can be done efficiently, and it finds notable applications in graph algorithms and in particular in graph drawing. On the other hand, finding an st-orientation with at most k transitive edges is more challenging and it was recently proven to be NP-hard already when k = 0. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.

Cite as

Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, and Tommaso Piselli. On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.MFCS.2023.18,
  author =	{Binucci, Carla and Liotta, Giuseppe and Montecchiani, Fabrizio and Ortali, Giacomo and Piselli, Tommaso},
  title =	{{On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.18},
  URN =		{urn:nbn:de:0030-drops-185524},
  doi =		{10.4230/LIPIcs.MFCS.2023.18},
  annote =	{Keywords: st-orientations, parameterized complexity, graph drawing}
}

Search Results

Documents authored by Piselli, Tommaso

On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges

Abstract

Cite as

Thanks for your feedback!

Could not send message